package sample.algo.sistr.algosample.algos.avl;

import android.util.Log;

public class Node <E extends Comparable<E>> {

    public Node<E> father;
    public final E val;
    public Node<E> r; // right son
    public Node<E> l; // left son

    public int leftHeight;
    public int rightHeight;

    public final boolean autoBalance;

    public Node(E val) {
        father = null;
        this.val = val;
        r = null;
        l = null;
        leftHeight = rightHeight = 0;
        autoBalance = false;
    }

    public Node(E val, boolean autoBalance) {
        father = null;
        this.val = val;
        r = null;
        l = null;
        leftHeight = rightHeight = 0;
        this.autoBalance = autoBalance;
    }

    // return the (new) root of the tree (may happen during rebalance)
    public Node<E> Add(E v) {
        if(val.compareTo(v) > 0) {
            // v is inferior to val so it goes to left side
            if(l == null) {
                l = new Node<E>(v, autoBalance);
                l.father = this;
                leftHeight++;
            }
            else {
                l.Add(v);
                leftHeight = Math.max(l.leftHeight, l.rightHeight) + 1;
            }
        }
        else {
            // v is superior or equal to val, it goes to the right side
            if(r == null) {
                r = new Node<E>(v, autoBalance);
                r.father = this;
                rightHeight++;
            }
            else {
                r.Add(v);
                rightHeight = Math.max(r.leftHeight, r.rightHeight) + 1;
            }
        }

        if(Math.abs(rightHeight-leftHeight) >= 2.0 && this.autoBalance){
            Log.d("algosample", "Rebalancing ...");
            if (rightHeight-leftHeight == -2) { // left tree height > right tree height
                if (this.l.rightHeight - this.l.leftHeight == 1) { //The "Left Right Case"
                    Log.d("algosample", "Left Right Case");
                    this.l.RotationLeft();
                }
                Log.d("algosample", "Left Left Case");
                //Left Left Case
                this.RotationRight();
                return this.father;
            } else { // left tree height < right tree height
                if (this.r.rightHeight - this.r.leftHeight == -1) { //The "Right Left Case"
                    this.r.RotationRight(); //reduce to "Right Right Case"
                }
                //Right Right Case
                this.RotationLeft();
                return this.father;
            }
        }
        return this;
    }

    public Node<E> RotationRight() {
        // return if current node does not have a left son
        if(this.l == null)
            return this;

        // 1 : father of the current node become the father of its left son.
        l.father = this.father;
        if(l.father != null) {
            if (l.father.l == this)
                l.father.l = r;
            else
                l.father.r = r;
        }

        // 2 : father of the current node become left son
        this.father = this.l;

        // 3 : current node left son become left-son-right-son
        this.l = this.l.r;

        // 4 : ex left son (now current node father) right son become the current node
        this.father.r = this;

        // Update heights
        // Current node left height is height of left son + 1
        this.leftHeight = (this.l != null)?Math.max(this.l.leftHeight, this.l.rightHeight) + 1:0;
        // Father right height is current node height + 1
        this.father.rightHeight = Math.max(this.leftHeight, this.rightHeight) + 1;

        return this.father;
    }

    public Node<E> RotationLeft() {
        // return if current node does not have a right son
        if(this.r == null)
            return this;

        // 1 : father of the current node become the father of its right son.
        r.father = this.father;
        if(r.father != null) {
            if (r.father.l == this)
                r.father.l = r;
            else
                r.father.r = r;
        }

        // 2 : father of the current node become right son
        this.father = this.r;

        // 3 : current node right son become right-son-left-son
        this.r = this.r.l;

        // 4 : ex right son (now current node father) left son become the current node
        this.father.l = this;

        // Update heights
        this.rightHeight =(this.r != null)?Math.max(this.r.leftHeight, this.r.rightHeight) + 1:0;
        this.father.leftHeight = Math.max(this.leftHeight, this.rightHeight) + 1;

        return this.father;
    }
}
